package com.labuladong;

/**
 * 项目名称: java_algorithm
 * @ClassName Nqueen
 * @Description N皇后问题
 * @Author huipanxing huipanxing@chinasofti.com   @Date 2022/6/20 18:00
 */
public class Nqueen {

    public static void main(String[] args) {
        System.out.println(num(8));
    }

    public static int num(int n) {
        if (n <= 0) {
            return 0;
        }

        int[] record = new int[n];
        return process(0, record, n);
    }

    private static int process(int i, int[] record, int n) {
        //如果能走到最后一行 说明成功一次
        if (i == n) {
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            if (isValid(record, i, j)) {
                //标记合法的坐标点  i为横坐标  j为纵坐标
                record[i] = j;
                res += process(i + 1, record, n);
            }
        }
        return res;
    }

    private static boolean isValid(int[] record, int i, int j) {
        //遍历之前的数据 k表示行
        for (int k = 0; k < i; k++) {
            //共列和共斜线
            if (j == record[k] || Math.abs(i - k) == Math.abs(j - record[k])) {
                return false;
            }
        }
        return true;
    }
}
